def merge_sort(nums: list[int]) -> list[int]:
    if len(nums) <= 1:
        return nums
    
    # 分割数组
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])  # 递归排序左半部分
    right = merge_sort(nums[mid:])  # 递归排序右半部分

    # 合并两个已排序的数组
    return merge(left, right)

def merge(left: list[int], right: list[int]) -> list[int]:
    sorted_array = []
    i = j = 0
    
    # 合并两个有序数组
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_array.append(left[i])
            i += 1
        else:
            sorted_array.append(right[j])
            j += 1
    
    # 处理剩余的元素
    sorted_array.extend(left[i:])
    sorted_array.extend(right[j:])
    
    return sorted_array

if __name__ == "__main__":
    nums = [5, 2, 9, 1, 5, 6]
    print(merge_sort(nums))  # 输出 [1, 2, 5, 5, 6, 9]
